#include <iostream>
#include <stdio.h>
#include <queue>
#include <stdlib.h>
#include <vector>
#include <assert.h>
using namespace std;

typedef struct BinaryTreeNode
{
  struct BinaryTreeNode* left;
  struct BinaryTreeNode* right;
  int val;
}BTNode;

BTNode* BuyNode(int x)
{
  BTNode* node = (BTNode*)malloc(sizeof(BTNode));
  if(node == NULL){
    perror("malloc fail\n");
    exit(-1);
  }

  node->val = x;
  node->left = NULL;
  node->right = NULL;


  return node;
}

void PreOrder(BTNode* root)
{
  if(root == NULL){
    //printf("NULL");

    return;
  }

  printf("%d ",root->val);
  PreOrder(root->left);
  PreOrder(root->right);
}

void InOrder(BTNode* root)
{
  if(root == NULL)
  {
    //printf("NULL");
    return;
  }

  InOrder(root->left);
  printf("%d ",root->val);
  InOrder(root->right);
}


void PostOrder(BTNode* root)
{
  if(root == NULL)
  {
    //printf("NULL");
    return;
  }

  PostOrder(root->left);
  PostOrder(root->right);
  printf("%d ",root->val);
}

int TreeSize(BTNode* root)
{
  return root == NULL ? 0:1+TreeSize(root->left) + TreeSize(root->right);
}

int TreeLeaSize(BTNode* root)
{
  if(root == NULL){
    return 0;
  }

  if(root->left == NULL && root->right == NULL)
  {
    return 1;
  }

  return TreeLeaSize(root->left) + TreeLeaSize(root->right);
}

int TreeKLea1(BTNode* root, int k)
{
  assert(k > 0);

  if(root == NULL)
  {
    return 0;
  }

  if(k == 1)
  {
    return 1;
  }

  return TreeKLea1(root->left,k-1) + TreeKLea1(root->right, k-1);
}

void TreeDestroy(BTNode* root){
  if(root == NULL){
    return;
  }

  TreeDestroy(root->left);
  TreeDestroy(root->right);
  free(root);

}

BTNode* TreeFind(BTNode* root,int x){
  if(root == NULL){
    return NULL;
  }

  if(root->val == x){
    return root;
  }

  BTNode* ret = TreeFind(root->left,x);
  if(ret){
    return ret;
  }

  ret = TreeFind(root->right,x);
  if(ret){
    return ret;
  }

  return NULL;
}

class TreeNodePostOrder{
  public:
  void BTNodePostOrder(BTNode* root){
    queue<BTNode*> q;
    vector<int> v;
    if(root){
    q.push(root);
  }

  while(!q.empty()){
    v.push_back(root->val);
    if(root->left){
      q.push(root->left);
    }

    if(root->right){
      q.push(root->right);
    }

    q.pop();
  }

  cout << endl;

}

};

int TreeComplete(BTNode* root){
  queue<BTNode*> q;
  if(root){
    q.push(root);
  }
    while(!q.empty()){
      BTNode* front = q.front();
      if(front == NULL){
        break;
      }

      q.push(root->left);
      q.push(root->right);
      q.pop();
    }

    while(!q.empty()){
      BTNode* front = q.front();
      q.pop();
      if(front != NULL){
        return false;
      }
    }

    return true;
}


int main()
{
  BTNode* node1 = BuyNode(1);
  BTNode* node2 = BuyNode(2);
  BTNode* node3 = BuyNode(3);
  BTNode* node4 = BuyNode(4);
  BTNode* node5 = BuyNode(5);
  BTNode* node6 = BuyNode(6);

  node1->left = node2;
  node1->right = node4;
  node2->left = node3;
  node2->right = node5;
  node4->right = node6;

  printf("前序：");
  PreOrder(node1);
  printf("\n");
  
  printf("中序：");
  InOrder(node1);
  printf("\n");

  printf("后续：");
  PostOrder(node1);
  printf("\n");

  printf("总节点个数：");
  int size1 = TreeSize(node1);
  printf("%d ",size1);
  printf("\n");

  printf("叶子节点个数：");
  int size2 = TreeLeaSize(node1);
  printf("%d ",size2);
  printf("\n");

  printf("第K层节点个数:");
  int size3 = TreeKLea1(node1,3);
  printf("%d ",size3);
  printf("\n");

  BTNode* ret =TreeFind(node1,4);
  cout << ret->val << endl;


  return 0;
}
